package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-25 19:02
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 相交链表
 * <p>
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null 。
 */
public class lc160 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode tmpA = headA;

        while (tmpA != null) {
            set.add(tmpA);
            tmpA = tmpA.next;
        }

        ListNode tmpB = headB;
        while (tmpB!=null){
            if (set.contains(tmpB)){
                return tmpB;
            }
            tmpB = tmpB.next;
        }

        return null;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
